package com.leetcode.根据算法进行分类.排序算法相关.归并排序;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2020/12/30
 * @description: 21. 合并两个有序链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 */
public class A_21_合并两个有序链表 {


	/**
	 * 链表就不需要去创建额外的空间了
	 *
	 * @param l1
	 * @param l2
	 * @return
	 */
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		//虚拟一个哨兵节点
		ListNode guard = new ListNode(0);
		ListNode cur1 = l1;
		ListNode cur2 = l2;
		ListNode pre = guard;
		while (cur1 != null && cur2 != null) {
			if (cur1.val < cur2.val) {
				pre.next = cur1;

				cur1 = cur1.next;
			} else {
				pre.next = cur2;

				cur2 = cur2.next;
			}
			pre = pre.next;
		}

		if (cur1 == null) {
			pre.next = cur2;
		}
		if (cur2==null){
			pre.next = cur1;
		}
		return guard.next;
	}
}
